Ray tracing involves a technique for determining the visibility of an object or objects from a given point, such as, but not limited to, an “eye” or “camera” point, by following a ray. While such techniques theoretically can involve testing a vast number of rays against each and every primitive, this is typically not practical. Instead, designers have used various data structures to identify a subset of such primitives to be involved in the testing, thereby reducing required processing. Examples of such data structures include bounding volume hierarchies (BVHs), kd-trees (k-dimensional trees), binary space partitioning (BSP) trees, etc.
Many techniques have been utilized for constructing such data structures in the past. However, such techniques have focused mainly on building binary data trees. Additionally, existing techniques typically construct the data trees during a pre-processing step where data trees are assumed to be constructed offline and only traversed at render time. There is thus a need for addressing these and/or other issues associated with the prior art.